// 79.单词搜索
// https://leetcode.cn/problems/word-search/description/
// 回溯
// 这道题是回溯吗？

/**
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

 */

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    globalInfo.board = board;
    globalInfo.word = word;
    globalInfo.rows = board.length;
    globalInfo.cols = board[0].length;

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            const startPoint = board[i][j];
            if (backTracking(i, j, 0, '')) {
                console.log('GOTCHA');
                return true;
            }
        }
    }
    console.log('NO FOUND');
    return false;
};

var globalInfo = {
    board: null,
    word: '',
    rows: 0,
    cols: 0,
};

var backTracking = function (
    boardRow,
    boardCol,
    wordIndex,
    tempWord = '',
    stepLog = new Set()
) {
    if (boardRow < 0 || boardRow >= globalInfo.rows) return false;
    if (boardCol < 0 || boardCol >= globalInfo.cols) return false;

    const key = `${boardRow}-${boardCol}`;
    if (stepLog.has(key)) return false;

    if (globalInfo.board[boardRow][boardCol] !== globalInfo.word[wordIndex])
        return false;

    tempWord += globalInfo.board[boardRow][boardCol];
    stepLog.add(key);

    if (tempWord === globalInfo.word) return true;

    console.log(`GOT ${tempWord}`);

    // 上
    const u_Row = boardRow - 1;
    const u_Col = boardCol;

    // 下
    const d_Row = boardRow + 1;
    const d_Col = boardCol;

    // 左
    const l_Row = boardRow;
    const l_Col = boardCol - 1;

    // 右
    const r_Row = boardRow;
    const r_Col = boardCol + 1;

    let ret1 = backTracking(u_Row, u_Col, wordIndex + 1, tempWord, stepLog);
    let ret2 = backTracking(d_Row, d_Col, wordIndex + 1, tempWord, stepLog);
    let ret3 = backTracking(l_Row, l_Col, wordIndex + 1, tempWord, stepLog);
    let ret4 = backTracking(r_Row, r_Col, wordIndex + 1, tempWord, stepLog);

    const ret = ret1 || ret2 || ret3 || ret4;
    if (!ret) {
        stepLog.delete(key);
    }

    return ret;
};

/**
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

 */

exist(
    [
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E'],
    ],
    'ABCCED'
);

exist(
    [
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E'],
    ],
    'SEE'
);

exist(
    [
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E'],
    ],
    'ABCB'
);
exist(
    [
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'E', 'S'],
        ['A', 'D', 'E', 'E'],
    ],
    'ABCESEEEFS'
);
